Software application programs, such as word processors, are generally configured to create page-based documents where each page contains document data such as graphical objects (e.g. text, images), represented by lines and fill regions. When representing the document data on a display device or a printing device, such software application programs generally use the graphics interface services of a host operating system to send commands describing graphical objects to the display or printing device. Such graphics interface services are referred to herein as a ‘graphics device interface layer’ and are generally configured as an application software programming interface which provides a rich set of graphics features to all applications executing on the host operating system.
One role of the graphics device interface layer is to mediate between an application program and an output device, such that the graphics device interface layer requires one or more device layers. One such device layer is referred to herein as a ‘device driver’, and is configured to support a relatively small set of functionality, such as drawing rectangular blocks of image data, and/or filling simple regions with flat color. The graphics device interface layer generally provides graphical objects to the device driver in a format that the graphics device interface layer considers is the most efficient for the device driver, and at the resolution of the output device. For example, a square of ten units by ten units positioned at the top left of a page of size twenty units by twenty units, may be rendered by a software application onto an A4 page (i.e. 210 mm by 297 mm) at 600 dpi, such that the graphical object is given to the device driver as a ‘path’ of five points (0,0), (2480,0), (2480,2480), (0, 2480), (0,0) where all of these points represent pixel values. The term path as used herein refers to a series of line segments, where each line segment consists of at least two points, such that each line segment traces the outline of a region (e.g. a graphical object) on a page.
Another device layer which is often referred to as a ‘graphics rendering system’, renders graphical objects received from the graphics device interface layer by generating pixel values. The term ‘rendering’ as used herein refers to the process by which graphical objects received from the graphics device interface layer are converted to pixels by the graphics rendering system.
In some computer systems, rendering is a two-stage process where graphical objects are firstly converted into an intermediate format before actual rendering can begin. In one such system, the first stage of the process is to convert each graphical object received from the graphics device interface layer into an intermediate edge-based object graphics format, such that the edges defining the outline of a graphical object are sorted into ascending y-value order, and then into ascending x-value order, assuming a raster scan order of rendering. The output from this first stage is a display list of edges and their associated fill and priority information level (i.e. ‘z-order’), along with other information such as whether a particular edge is a clipping edge or a filling edge. The display list is generally referred to as a ‘job’ and contains all of the information needed to render a page.
The z-order refers to the priority order in which a graphical object is to be rendered within a total set of graphical objects to be rendered for a page. A graphical object having a higher priority can obscure a graphical object having a lower priority, if the graphical object having the higher priority object is opaque. If the higher priority graphical object is semi-transparent, then any of the graphical objects having a lower priority and being positioned beneath the higher priority object can contribute color to the higher priority graphical object when rendered.
The second stage of the rendering process consists of a rendering module ‘parsing’ the job for a page and generating pixels associated with each scan-line of the page to be rendered. The term parsing refers to the process of deciding whether a string of input symbols is in a given format and if so determining the syntactic structure of the string as defined by that format.
In a graphics rendering system using z-order priority, the edges defining the outlines of a graphical object are monotonically increasing in the direction of rendering, with respect to a scan-line crossing the graphical object. Priority information associated with each of the graphical objects for such a graphics rendering system generally consists of fill data (e.g. a bitmap, a flat color or a tiled image) and an associated fill rule (e.g. non-zero winding or odd-even fill rule). The priority information also comprises a priority value, where the object having the lowest priority has an associated priority value of zero. Further, each of the graphical objects of such a system has information for compositing a particular graphical object onto other graphical objects having a lower priority and which are associated with the graphical objects. Still further, each edge being crossed by a scan-line at a particular point is considered to have a current x-coordinate value, and is considered to be part of a set of active edges for the scan-line
Once the above priority information has been determined for all of the graphical objects to be rendered for a page, the edges of the objects are sorted into ascending y-value and ascending x-value order before rendering begins. To then render a scanline, a variable X, representing a pixel position on the scanline, is set to zero and then starting with the first edge in a list of active edges for the scanline, the activating and deactivating priority values associated with each of the edges are processed according to a fill rule until an edge is found with a current x-value which is greater than the variable X (i.e. the next edge to process). Pixels between the position defined by the variable X and the current x-value are then output according to any active objects that fall within the position. If no objects are active in the defined positions then white space is output and the variable X is set to the current x-value. The remaining edges for the scanline are then processed in a similar manner.
The result of processing all object edges crossed at the same point for a particular scanline, is a list of active objects and their associated priority values for that point. The list is sorted from the object having the lowest associated priority value to the object having the highest associated priority value, such that the priority object having the lowest associated priority value is the top-most opaque object. The final resulting color for a pixel run beginning at the crossed edge is then determined by compositing the fill colors of the two lowest priority objects, then compositing the result of this with the fill color of the object having the next highest priority value, and then continuing in a similar manner until the fill color for the object having the highest associated priority value has been composited. For example, FIG. 5 shows a page 500 to be rendered. The page 500 consists of two opaque objects (i.e. squares 501 and 503) on a white background 505. In the example, of FIG. 5, the page 500 is fifty pixels wide. A list of active edges for the scanline 507 on the page 500, arranged in ascending x-value order, is as follows:
(i) edge 509 having a current x-value equal to fifteen;
(ii) edge 511 having a current x-value equal to twenty one;
(iii) edge 513 having a current x-value equal to twenty seven; and
(iv) edge 515 having a current x-value equal to forty.
There are five pixel runs identified for the scanline 507. The five pixel runs for the scanline 507 in order are as follows:
(i) 0 to edge 509;
(ii) Edge 509 to edge 511;
(iii) Edge 511 to edge 513;
(iv) Edge 513 to edge 515; and
(v) Edge 515 to the end of the scanline 507 (i.e. Pixel 50).
In order to render the scanline 507, initially a variable X is set to zero. At edge 509, the current x-value is equal to 15 which is greater than the value of X and pixels between X=0 and X=15 are output (i.e. white pixels as no objects are active). The variable X is then set to fifteen and the object 501 has an active priority (i.e. ActivePriorityList=Object 501). At the next edge 511, the current x-value is equal to 21 which is greater than the value of X and pixels between edge 509 and edge 511 are output according to the fill of object 501. The variable X is then set to twenty-one and the object 503 has an active priority (i.e. ActivePriorityList=Object 501, Object 503).
The rendering process for the scanline 507 continues at the next edge 513, where the current x-value is equal to twenty-seven which is greater than the value of X and pixels between edge 511 and edge 513 are output according to the fill of priority object 503. The variable X is set to twenty-seven and object 501 is deactivated (i.e. ActivePriorityList=Object 503). At the next edge 515, the current x-value is equal to forty which is greater than the value of the variable X and pixels between edge 513 and edge 515 are output according to the fill of object 503. The variable X is then set to forty and object 503 is deactivated (i.e. ActivePriorityList=Empty). There are no more edges and therefore, the rendering of scanline 507 is completed with white space pixels being output up until the end of scanline 507.
In the example of FIG. 5, two objects (i.e. 501 and 503) were active between edges 511 and 513. However, since object 503 is opaque, only the pixels of object 503 contribute to the final image between the edges 511 and 513. Thus, regardless of the number of active objects for a pixel run, if the top-most object is opaque, then only the fill for this object needs to be output.
As another example, FIG. 6 shows a scanline 601, crossing three objects 602, 603 and 604. In the example of FIG. 6, object 604 is semi-transparent, meaning any objects underneath the object 604 may contribute color when the object 604 is rendered. In this case, object 603 is opaque and is the only object that contributes to the color of the object 604. The edge-list for the scanline 601 is as follows:
edge 605, edge 607, edge 609, edge 611, edge 613 and edge 615.
For the pixel run between edges 609 and 611, the objects 602, 603 and 604 are active. However, since object 603 is opaque, only the pixels for object 603 and object 604 need to be composited, since object 603 is the top-most opaque object (i.e. object 603 is the opaque object having the highest associated priority value).
The result of processing all edges crossing the same point on a scanline is generally a list of the active objects sorted from the object having the lowest associated priority value to the object having the highest associated priority value, such that the object having the lowest priority value is the top-most opaque object. The final color is then determined by compositing the fill color of the two objects having the lowest associated priority values, then compositing the result of composition with the object having the next highest priority value, and then continuing until the object having the highest associated priority value has been composited.
One known method of rendering an image using priority information is to maintain an active priority list as a linked list of objects and associated priority values. In accordance with this known method, the linked list is sorted using a method known as ‘in-place’ sorting. When a particular object is activated for a scanline, this object is inserted into the active linked list in sorted order depending on the associated priority value for the object. Conversely, when an object is deactivated, the deactivated object is removed from the active linked priority list. After all of the object edges for a pixel run have been processed, the top-most-opaque object is determined by traversing the active linked priority list from the object having the highest associated priority value to the object having the lowest associated priority value until an opaque object is found, or until all of the objects in the list have been traversed. Although this known method of rendering an image is suitable for small numbers of active objects, performance for the method deteriorates markedly when a large number of objects are activated simultaneously. In such a case each object is inserted into the active priority list and sorted for a given scanline. If the object edges crossed by the scanline occur such that the associated priority value for each edge is greater than the associated priority value of the next object edge, then rendering for the scanline would have an n2 order of complexity where n represents the number of object edges crossed.
Further, in the above described method using an active linked priority list, the same object may have to be added to the list multiple times, since an object can cross a scanline at the same point multiple times. For example, FIG. 7 shows a scanline 701 scanning an object 703. In scanning the object 703, the scanline 701 crosses four edges 705, 707, 709 and 711. For ease of explanation, FIG. 7 also shows the edges 705, 707, 709 and 711 graphically separated from the object 703. The edges 705, 707, 709 and 711 can be processed for the scanline 701 as follows:
(i) Get edge 705 and activate object 703;
(ii) Get edge 707 and deactivate object 703;
(iii) Get edge 709 and activate object 703; and
(iv) Get edge 711 and output a pixel run up to edge 711 with fill associated with object 703 since object 703 is active.
Hence, removing an object and associated priority value from a sorted priority list is inefficient if the object must be reinserted again at a later time. However, in order to address the inefficiency of reinserting objects into a priority list, a further known method of rendering an image using priority information maintains an active priority list as a linked list of objects and associated priority values and when an object is activated, the object is marked as being active. Conversely, in accordance with this further known method, when an object is deactivated, then the object is marked as being inactive but the object is not removed from the priority list. When the object is reactivated, then the object is marked as being active, and so on. When all of the object edges for a scanline have been processed fox a pixel run, then all deactivated objects are removed from the list, and an active top-most opaque object is found in a similar manner to the method discussed above.
The method of marking an object as either active or inactive is more efficient than the method of removing an inactive object from a priority list since an object can be activated and deactivated several times without needing to be reinserted into the priority list. However, the method of marking objects does not improve performance when a large number of objects are activated simultaneously as discussed above.
Still another known method of rendering objects using priority information, maintains an active priority list as a linked list of objects and associated priority values and when an object is activated, the object is added to the head of the priority list. Conversely, using this further method, when an object is deactivated, the object is removed from the priority list. When all of the object edges have been processed for a pixel run, the linked list of objects is sorted and since the list contains only activated objects, the list can be traversed to determine a top-most opaque object (i.e. the opaque object having the highest associated priority value). However, the disadvantage of this still further method is the complexity of sorting the linked list of objects and associated priority values. Further, this method of adding a priority object to the head of a priority list requires a large amount of memory since ideally such a method uses a doubly linked list requiring a next pointer and a previous pointer. In a sixty-four bit computer architecture the next and previous pointers both require eight bytes each, for each priority object. For example if there are 32000 priority objects, and all of the objects were activated, then there would be at least 512000 bytes (i.e. 512K) of memory required simply for pointers to manage the doubly linked list.
Still another known method of rendering objects using priority information, maintains an array of memory based on the size of the largest possible priority value, N. In this method, an active priority list of size N is provided. When a priority object is activated, an active priority list priority number, associated with the activated priority object, is set to TRUE. When a priority object is deactivated, the active priority list priority number, associated with the deactivated priority object, is set to FALSE. Once all of the object edges for the scanline have been processed, starting at the end of the active list (i.e. the highest priority value), the first active priority object is determined by traversing the list until an entry, i, in the active priority list is equal to TRUE, for 0≦i≦(N−1). If the object for the selected entry is opaque, then the traversal of the list is concluded. Otherwise, the list is again traversed from the object having highest associated priority value to the object having the lowest associated priority value until such an entry having an associated opaque object is found. For example, FIG. 8 shows an active priority list 800 where entries in the list (e.g. 801) representing the priority of associated objects numbered one to twenty, have been set to either TRUE or FALSE. In the example of FIG. 8, starting at the object having the highest associated priority value (i.e. twenty) the list 800 is traversed looking for the first TRUE entry 802 (i.e. the object having a priority value of eighteen). If the object associated with the priority value eighteen is not opaque, then the traversal of the list 800 is continued until the next TRUE entry 803 (i.e. the object having a priority value of eleven) is found. If the object having the associated priority value eleven is not opaque, then the traversal of the list 800 continues until the object having the associated priority value of eight is found. Assuming that object having the associated priority value of eight is opaque, then the fill colors from objects having associated priority values of eight and eleven are composited with the resulting fill color being composited with the fill color of the object having the associated priority value of eighteen and the resulting color is output.
One problem of the method of setting each object in an active priority list as TRUE or FALSE is that the method is required to perform a large number of memory accesses. For example, in a case where there are 32000 possible objects then all 32000 entries may potentially have to be searched after any edge has been processed. To avoid this problem, when a priority object is activated, the active object having the maximum associated priority value can be retained (e.g. by setting a variable MaxPriority=max(MaxPriority, activated priority number)) during processing. However, in this case, if the maximum priority activated was, for example, number thirty two thousand, followed by number three, then number two and number one, then the entire list must still be traversed before the entry for object having the associated priority value of number two is determined as the next active object.
Finally, still another known method of rendering objects using priority information, maintains an array of memory based on the size of the largest possible priority value, N, where each TRUE or FALSE entry is of size one bit. Therefore, since TRUE and FALSE only require the value one or zero, only a single bit is needed to distinguish between an active object and a non-active object in an active priority list. FIG. 9 shows an active priority list 900 where each of the entries (e.g. 901) for objects numbered one to twenty have an associated bit (e.g. 902), where one represents TRUE and zero represents FALSE. The values of the bit entries corresponding to the objects, numbered one to twenty for the list 900, can be represented and stored in hexadecimal format as 0H11204. This method where each TRUE or FALSE entry is of size one bit is similar to the method described in the preceding paragraph, although the required memory search space has been reduced by a factor of eight. However, a significant speed penalty is still incurred using this one bit method, since a potentially large number of object entries may still be required to be traversed in order to find the opaque object having highest associated priority value.